#include <stdio.h>
#include <stdlib.h>

// 二分查找
int binarySearch(int arr[], int k, int len)
{
    int low = 0;
    int high = len - 1;

    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        printf("before----->mid=%d, low=%d, high=%d\n", mid, low, high);
        if (arr[mid] == k)
        {
            return mid;
        }

        if (arr[mid] > k)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
        printf("after----->mid=%d, low=%d, high=%d\n", mid, low, high);
    }

    return -1;
}

// 递归二分查找
int binarySearchRecur(int arr[], int low, int high, int k)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        if (arr[mid] < k)
        {
            return binarySearchRecur(arr, mid + 1, high, k);
        }
        return binarySearchRecur(arr, low, mid, k);
    }

    if(arr[low] == k){
        return low;
    }

    return -1;
}

int main()
{

    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    printf("find the value, the index is: %d", binarySearch(arr, 1, 8));
    printf("\n-----------not use recursion-----\n");
    printf("find the value, the index is: %d", binarySearchRecur(arr, 0, 7, 8));

    return 0;
}